package sort;

//插入排序，时间复杂度 O（n²），80000 数据 5s

import java.util.Arrays;

public class InsertionSort {
	public static void main(String[] args) {
		int array[] = {101, 34, 119, 1, -1, 99};
		insertSort(array);
	}

	//插入排序
	public static void insertSort(int[] array) {

		for (int i = 1; i < array.length; i++) {
			//定义待插入的数,
			int insertVal = array[i];
			int insertIndex = i - 1;

			//给 insertVal 找到插入的位置
			while (insertIndex >= 0 && insertVal < array[insertIndex]) {
				array[insertIndex + 1] = array[insertIndex];
				insertIndex--;
			}
			//当退出 循环时，表述插入的位置找到
			array[insertIndex + 1] = insertVal;

			System.out.println(Arrays.toString(array));
		}


	}
}
